# Full text of "Minimal three variable NOR and NAND logic circuits"

## See other formats

```

1 I B HAHY

OF THE
U N IVERSITY
Of ILLINOIS

510,84

I^6r

no. 156-163

c o p 2

r

^ATHEMP •

DIGITAL COMPUTER LABORATORY
UNIVERSITY OF ILLINOIS
URBANA, ILLINOIS

REPORT NO, 162

MINIMAL THREE-VARIABLE "NOR" AND "NAND" LOGIC CIRCUITS

by
Robert Allan Smith

May 15, 196k

(This work is being submitted in partial fulfillment of the requirements for
the Degree of Master of Science. )

MTHEMA1
LIBRARY

Digitized by the Internet Archive
in 2013

http://archive.org/details/minimalthreevari162smit

ACKNOWLEDGMENT

The author wishes to express his sincere thanks to Professor
To A, Murrell, his thesis advisor, for assistance in the preparation of this
thesis.

Return this book on or before the
Latest Date stamped below.

Theft, mutilation, and underlining of books
are reasons for disciplinary action and may
result in dismissal from the University.
University of Illinois Library

MAR B W87

L161— O-1096

Page

1. INTRODUCTION 1

2. DESCRIPTION OF THE PROGRAM 3

2.1 The Universal Circuit 3

2.2 Generation of Matrices k

2.3 Processing of Matrices 5

3. COMMENTS ON THE RESULTS .......... 6

k. TABLE OF RESULTS ................. 7

5. CIRCUIT DIAGRAMS . 18

6. CONCLUSIONS ...... 20

BIBLIOGRAPHY .... ................ 21

-in

MINIMAL THREE-VARIABLE "NOR" AND "NANIj" LOGIC CJ
Robert Allan Smith, M.S.
Department of Electrical Engineering
University of Illinois, 196^

This paper presents a table of minimal NOR and NAND combinational
circuits for the 256 logical functions of three variables, assuming complemented
inputs are available. The circuits were found by an exhaustive method, using a
computer. The criteria used for minimality were, first, minimality with respect
to the number of logic elements, and second, minimality with respect to the
total number of inputs to all elements, subject to the first condition. The
results show that all 256 functions can be generated using five or fewer NOR or
NAND elements.

■IV-

1. INTRODUCTION

Circuits composed of NOR or NAND elements, while not the fastest type
of circuits, are used extensively, mainly because of their economy--one type of
element may be used throughout an entire circuit. Assuming the basic decision
to use such "universal" elements has been made, the main design objective will
usually be to produce either the fastest or the most economical circuit possible.
The fastest NAND circuits, i.e., minimum levels, are obtained by rewriting the
minimum-OR polynomial (as obtained by the Quine-McCluskey method) in terms of
the NAND connective, yielding a three-level logic (two-level if complemented
inputs are available). Similarly the minimum- AND polynomial may be written in
terms of the NOR connective. Circuits obtained in this way are often also mini-
mal with respect to the number of logic elements required.

At present there are no known algebraic methods of obtaining absolutely
minimal NOR or NAND circuits, or for that matter, circuits using any other types

of logic elements. Methods such as the Quine-McCluskey method and the Karnaugh

1 3
map method ' give only near-to-minimal realizations. Recently, however,

2
Hellerman has reported the results of an exhaustive method utilizing a computer.

The criteria used for minimality were, first, minimality with respect to the

number of logic elements, and second, minimality with respect to the total number

of inputs to all elements, subject to the first condition. Complemented inputs

were assumed not available.

In Hellerman ' s approach, a universal circuit configuration was set up

which permitted systematic investigation of all the possible ways of connecting

together a given number of NOR elements . The program began by generating as many

functions as possible using one NOR element and storing the circuit configuration

and the number of inputs required, in memory. Then, all possible configurations

of two NOR elements were considered. If a particular function had been generated

-1-

previously with fewer elements or with the same number of elements but with
fewer inputs, the configuration under consideration was discarded. If the func-
tion had been generated previously with the same number of elements but with more
inputs, the information regarding the configuration and the number of inputs
replaced the previously stored information for that function. The program con-
tinued in this way, up to seven NOR elements, and yielded a catalog of minimal
NOR realizations for the 256 logical functions of three variables. Minimal NAND
realizations were derived from the set of NOR realizations.

The results reported in this thesis form an extension of Hellerman's
work. A similar catalog is given, with the difference being that complemented
inputs are assumed available. The same minimality criteria are used. The
results show that with complemented inputs, all 256 functions can be generated
using five or fewer NOR or NAND elements.

2. DESCRIPTION OF THE PROGRAM

The computer program was written in the assembler language SCATRE
and was run on the IBM 709^+, the total running time being approximately
35 minutes. The program considered NAND circuits rather than NOR circuits, and
began with one NAND element, continuing up to four NAND elements,

2.1 The Universal Circuit

The universal circuit which allowed investigation of all possible
configurations of four NAND elements is shown in Fig„ 1.

Inputs
a b c a b c

123^56 7 89

FIGURE 1. THE UNIVERSAL CIRCUIT

Output

Crossover points are either connected or disconnected, indicating which
inputs feed the various elements. The circuit is then representable by a connec-
tion matrix, a matrix of ones and zeros, each element of which indicates the
presence or absence of a connection at the corresponding point in the circuit „

A separate computer word was used to represent each row of the matrix. Since

30 ^ 9
each connection point has two possible values, there are 2 ~ 10 possible

-3-

connection matrices. Many of these will, however, result in useless circui'
and there are a number of restrictions which may be placed on the form of the
connection matrix to eliminate these. Some restrictions are difficult to incor-
porate into a program and some effect only a small saving of time. The following
three restrictions were used in the final program:

1. An input and its complement (e.g. , a and a) were not allowed
to be fed into the same NAND element.

2. Columns 1, 2, and 3 were "ordered," i.e., if A, B, and C
represent the values of columns 1, 2, and 3 when considered
as binary numbers, then it was required that

A > B > C

This means that the program investigated only one member
from each of the 80 equivalence classes of functions of
three variables, i.e., one member from each set of con-
nection matrices whose members differ only in that they
effect a permutation of input variables.

3. Each element in the circuit had to be "useful," i.e., the
output of every element (except the last) had to feed some
other element.

The number of matrices connecting four NAND elements which will pass
the above restrictions is approximately 5 X 10 > a considerable saving over the
original number.

2.2 Generation of Matrices

The systematic generation of matrices connecting four NANB elements
was carried out as follows. Because of restriction 3j there are only 21 possible
partial matrices consisting of columns 7, 8, and 9° These were stored in memory

to be added to the remaining portion of the matrix. Because of restriction 1,
there are only 27 permissible ways of "filling" the portion of any row up to
column 6. These were similarly stored in 27 words. An outer program loop
selected one of the 21 partial matrices for columns 7> 8, and 9- Inner loops
systematically selected partial rows from the 27 possible ones, such that all
combinations were exhausted. After generation of a particular matrix, columns 1,
2, and 3 were checked for ordering. If ordering was present the matrix was
"processed" to determine what logical function it produced; if not, a new matrix
was generated.

2.3 Processing of Matrices

The processing of a given matrix was the key portion of the program
since it was repeated so many times; hence it had to be made as economical as
possible. The basic method of processing was the same as used by Hellerman,
i.e., the output of the circuit was determined for each of the eight possible
input combinations. The sequence of machine instructions used to accomplish
this was different however, and is thought to be as efficient as possible, A
given input combination was placed in the sense-indicator (Si) register. Then
each bit position of the word for row 1 which was a one was compared with the
corresponding bit in the SI register, using the ONT (on-test for indicators)
instruction. If all corresponding positions were also one this meant that the
output of the NAND element in row 1 was zero, and the computer skipped the next
instruction. If any position was zero, this meant that the output of the NAND
element was a one, and the machine executed the next instruction, which placed
(via the OSI instruction) an additional one in the "column-7" position of the SI
reigster. This process was then repeated for the remaining rows.

Not all of the 256 functions of three variables were generated by the
circuits containing up to four NAND elements. Circuits for the ten remaining
functions were found and are included in the table of results. They all contain
five NAND elements and hence are minimal with respect to the number of elements,
but they may not be minimal with respect to the number of inputs.

The set of minimal NOR circuits is also given in Table 1. These
were obtained directly from the minimal NAND circuits using the fact that any
minimal NAND circuit realizing a function F(a,b,c) will also represent a minimal
NOR circuit for the function G(a,b,c) where

F(a,b,c) = G(a,b,c)

-6-

h, TABLE OK RESULTS

Table 1 lists the minimal NOR and NAND realizations for the
256 functions of three variables, assuming complemented inputs are available.
The functions are listed according to an octal number which indicates which
minterms are present in the canonical expansion of the function, Writing a
given octal designation number as an 8-bit binary number (filling in left zeros
if necessary), the bits, from left to right, indicate the presence or absence of
the terms abc, abc, abc, abc, abc, abc, abc, abc.

The circuit numbers and the corresponding inputs refer to the circuit
diagrams following the table. A circuit number of zero indicates that the
function requires no NAND element--it is either just a single literal or iden-
tically zero or one.

Several functions have two minimal realizations. In such cases the
alternative realization is listed immediately following the main entry.

-7-

TABLE 1.

Fen.

NAND

Inputs

NOR

Inputs

No.

Expression

Cct.

l

2

3

k

5

6789

Cct.

1

2

3

k

5 6 7 8 9

1

abc

3

a

b

c

2

a

b

c

2

abc

3

a

b

c

2

a

b

c

3

ab

k

a

b

1

a

b

k

abc

3

a

b

c

2

a

b

c

5

ac

k

a

c

1

a

c

6

a(bc+bc)

7

a

b

c

a

b

c

10

b

c

b

c

a

7

a(b+c)

6

b

c

a

5

b

c

a

10

abc

3

a

b

c

2

a

b

c

11

a(bc+bc)

7

a

b

c

a

b

c

10

c

b

b

c

a

12

ac

k

a

c

1

a

c

13

a(b+c)

6

b

c

a

5

c

b

a

Ik

ab

k

a

b

1

a

b

15

a(b+c)

6

c

b

a

5

b

c

a

16

a(b+c)

6

b

c

a

5

b

c

a

IT

a

a

a

20

abc

3

a

b

c

2

a

b

c

21

be

k

b

c

1

b

c

22

b(ac+ac)

7

b

c

a

b

c

a

10

a

c

a

c

b

23

b(a+c)

6

c

a

b

5

a

c

b

24

c ( ab+ab )

7

c

a

b

c

a

b

10

a

b

a

b

c

25

c ( a+b )

6

a

b

c

5

a

b

c

26

abc+abc+abc

11

a

b

c

a

b

c a b c

18

a

b

a

c

b c a b c

27

ab+ac+bc

12

b

c

a

b

c

12

b

c

a

b

c

30

abc+abc

7

a

b

c

a

b

c

15
16

b
b

c

a

a
c

b
a

c a
b c

31

abc+bc

8

b

c

a

b

c

Ik

12

b
a

c

c

a
b

b
b

c
c

32

ac+abc

8

a

c

a

b

c

<

Ik
12

a

b

c

c

b

a

a
a

c
c

33

ac+bc

9

b

c

a

c

9

a

c

b

c

TABLE 1 (CONT'D).

Fcn<
No.

Expression

NAND Inputs N ffl
Cct. 12 3 4 5 6 7 8 9 Cct,

Inputs
123456789

34

45

kG

ab+abc

35

ab+bc

36

a(b+c)+abc

37

a+bc

l+O

abc

l+l

b(ac+ac)

1+2

be

43

b(a+c)

kk

abc+abc

abc+ac

bc+abc

hi

bc+ac

50

abc+abc

51

abc+abc+abc

52

c ( a+b )

53

c(a+b)+ab

54

ab+abc

55

a(b+c)+abc

56

ab+bc

57

a+bc

60

ab

61

b(a+c)

62

b(a+c)

63

b

61+

ab+abc

a b a b c

9

a

b

c

b

13

b

c

a

b

c

a

5

b

c

a

3

b

c

a

7

b

c

a

b

c

a

1+

b

c

6

a

c

b

7

b

c

a

b

c

a

65

ab+ac

8 c a b c a

8 b c a b c

9 b c a c

7 a b c a b c

11 abcabcabc
6 abc

12 a b c a b

8 a b a b c

13 b c a b a c

9 abbe

5 b c a
1+ a b

6 a c b
6 cab
b

8 a b a b c

9 abac

11+
12

9
13

6
2

10
1
5
15
16
ll+

12
11+
12

9

10
18

5

12

11+

12

13

9

6

1

5

5

ik

12

9

a b

c b

b c

b c

b c

c a

c a

c b

c a

c a

c b

c a

b a

b c

a c

b c

a b

a b

a b

b c

a b

b c

b c

a b

c b

a b

a c

a c
b

b a

c a

a b

cab

a a b

b a

a b c a

a

b

cab

b

b c a b

a b c a

b c a

c c a

abc

b b c

a c

abc

a c b c a b c

c

abc

a c b

a a b

abac

b c

a

b
b

c b a
b b a
a c

TABLE 1 (CONT'D).

10

Fen,
No,

Expression

NAND Inputs NOR
Cct. 12 3 4 5 6 7 8 9 Cct,

Inputs
123456789

66 b(a+c)+abc

67 b+ac
70 ab+ab c

71

b(a+c)+abc

72

ab+ac

73

b+ac

74

ab+ab

75

ab+ab+ac

13

c a b c a b

15

cab

8

a b a b c

13

c

a

b

cab

6

a

c

b

1J+

b

a

b

c a

12

a

c

b

b a

13

a

c

b

a b c

9

a

b

a

c

6

a

c

b

9

a

b

a

b

8

a

b

c

a b

76

ab+ab+ac

a b a b c

77

a+b

100

abc

101

c( ab+ab)

102

abc+abc

103

abc+ab

104

be

105

c ( a+b )

106

bc+abc

107

bc+ab

110

abc+abc

111

abc+abc+abc

112

ac+abc

113

a(b+c)+abc

114

b ( a+c )

115

b(a+c)+ac

116

ac+bc

1

a

b

4

a

b

3

a

b

c

2

a

b

c

7

c

a

b

c

a

b

10

a

b

a

b

c

7

a

b

c

a

b

c

15

a

b

c

a

b

c

16

a

c

b

c

a

b

8

a

b

c

a

b

14

12

a
c

b

b

c

a

a
a

b
b

4

b

c

1

b

c

6

a

b

c

5

b

a

c

8

b

c

a

b

c

14
12

c
a

b
b

a
c

c
c

b
b

9

b

c

a

b

9

b

a

b

c

7

a

b

c

8

b

c

10

a

c

a

c

b

11

a

b

c

a

b

c a b c

18

a

b

a

c

b

c a b c

8

a

c

a

b

c

14
12

a
c

c

b

a

a

b
a

c
c

13

c

b

a

c

a

b

, !3

c

b

a

c

a

b

6

c

a

b

5

c

a

b

12

c

a

b

c

a

12

a

b

c

a

b

9

a

c

b

c

9

b

c

a

c

TABLE 1 (CONT'D).

Fen.

NAND

Inputs

NOR

Inputs

No.

Expression

Cct.

1

2

3

4

5

6 7 8 9

Cct.

1

2

3

4

5 6 7 8 9

117

a+bc

5

c

b

8

6

b

c

a

120

ac

4

a

c

1

a

c

121

c ( a+b )

6

b

a

C

5

a

b

c

122

ac+abc

8

a

c

a

b

c

14
12

c

b

a
a

b
c

c
c

a

a

123

ac+ab

9

a

c

a

b

9

a

b

a

c

124

c ( a+b )

6

a

b

c

5

a

b

c

125

c

c

c

126

c(a+b)+abc

13

a

b

c

a

b

c

13

a

b

c

a

b c

127

c+ab

5

a

b

c

6

a

b

c

130

ac+abc

8

a

c

a

b

c

14
12

c
a

a
b

c
c

b
c

a
a

131

c(a+b)+abc

13

a

b

c

a

c

b

13

a

b

c

a

c b

132

ac+ac

9

a

c

a

c

9

a

c

a

c

133

ac+ac+bc

14
12

c
c

a
b

c

a

a
c

b
a

8

a

c

a

b

c

134

ac+ab

9

a

c

a

b

9

a

b

a

c

135

c+ab

5

a

b

c

6

b

a

c

136

ac+ac+bc

14
12

c

b

a
c

b
a

c
c

a
a

8

a

c

a

b

c

137

a+c

1

a

c

4

a

c

140

abc+abc

7

a

b

c

a

b

c

10

b

c

b

c

a

i4i

abc+abc+abc

11

a

b

c

a

b

c a b c

18

a

c

b

c

a b a b c

ite

bc+abc

8

b

c

a

b

c

14
12

b
c

c

a

b
b

a
b

c
c

U3

b(a+c)+abc

13

c

a

b

c

b

a

13

c

a

b

c

b a

144

bc+abc

8

b

c

a

b

c

14
12

c
b

b

a

c
c

a
c

b
b

145

c(a+b)+abc

13

b

a

c

b

c

a

13

b

a

c

b

c a

146

bc+bc

9

b

c

b

c

9

b

c

b

c

147

bc+bc+ab

14
12

b

b

c

a

b
c

c

b

a
c

8

b

c

a

b

c

UNIVERSITY Of

TABLE 1 (CONT'D) .

Fen,

NAND

Inputs

NOR

Inputs

No.

Expression

Oct.

1

2

3

k

5

6

7

8 9

Cct.

1

2

3

k

5

6 7

89

150

abc+abc+abc

11

a

b

c

a

5

c

a

b c

18

a

b

a

c

b

c a

b c

151

c ( ab+ab ) +c ( ab+ab )

17

a

b

c

b

c

a

17

a

b

c

b

c

a

152

c(a+b)+abc

13

a

b

c

c

a

b

13

a

b

c

c

a

b

153

ac+ab+bc+abc

18

a

c

a

b

b

c

a

b c

11

a

b

c

a

b

c a

b c

15^

b(a+c)+abc

13

c

a

b

b

c

a

13

c

a

b

b

c

a

155

a(b+c)+bc+abc

18

b

c

a

c

a

b

a

b c

11

a

b

c

a

b

c a

b c

156

a(b+c)+bc+bc

11+
12

b
c

c

a

b

b

c

b

a
c

8

b

c

a

b

c

157

a+bc+bc

10

b

c

b

c

a

7

b

c

a

b

c

a

160

a(b+c)

6

b

c

a

5

b

c

a

161

a(b+c)+bc

12

b

c

a

b

c

12

c

a

b

c

a

162

bc+ca

9

b

c

c

a

9

a

c

b

c

163

b+ac

5

c

a

b

6

a

c

b

164

bc+ab

9

c

b

b

a

9

a

b

b

c

165

c+ab

5

b

a

c

6

a

b

c

166

bc+bc+ab

Ik
12

b
a

c

b

a
c

b
b

c
c

8

b

c

a

b

c

167

b+c

1

b

c

k

b

c

170

a(b+c)+abc

13

b

c

a

a

b

c

13

b

c

a

a

b

c

171

a(b+c)+abc+bc

18

a

b

a

c

b

c

a

b c

11

a

b

c

a

b

c a

b c

172

b(a+c)+ac+ac

Ik

12

c

a

a
b

c
c

a
c

b
a

8

c

a

c

a

b

173

b+ac+ac

10

c

a

c

a

b

7

c

a

b

c

a

b

17^

c ( a+b ) +ab+ab

Ik

12

a

b

b
c

a
a

b

a

c

b

8

a

b

a

b

c

175

c+ab+ab

10

a

b

a

b

c

7

a

b

c

8.

b

c

176

ab+bc+ac

15
16

a
b

b
c

c

a

a
b

b
a

c
c

7

a

b

c

a

b

c

177

a+b+c

2

a

b

c

-

3

a

b

c

200

abc

3

a

b

c

2

a

b

c

201

abc+abc

7

a

b

c

a

b

c

15
16

a

b

b
c

c
a

a

b

b
a

c
c

TABLE 1 (CONT'D).

Fen.

NAND

Inputs

NOR

Inputs

No.

Expression

Cct.

1

2

3

1+

5 6 7

8 9

Cct,

1

2

3

1+

5

6 7

8 9

202

c ( ab+ab )

7

a

b

c

a

b c

10

a

:

a

b

c

203

abc+ab

8

a

b

a

b

c

11+
12

a
b

b

c

a
a

b

a

c
b

201+

b(ac+ac)

7

c

a

b

c

a b

10

c

a

c

a

b

205

abc+ac

8

c

a

c

a

b

11+
12

c

a

a
b

c

c

a
c

b
a

206

abc+abc+abc

11

a

b

c

a

b c a

b c

18

a

b

a

c

b

c a

b c

207

abc+a(b+c)

13

b

c

a

a

b c

13

b

c

a

a

b

c

210

be

1+

b

c

1

b

c

211

abc+bc

8

b

c

a

b

c

11+
12

b
a

c
b

a
c

b

b

c
c

212

c ( a+b )

6

a

b

c

5

b

a

c

213

ab+bc

9

a

b

b

c

9

c

b

b

a

211+

b(a+c)

6

a

c

b

5

c

a

b

215

ac+bc

9

a

c

b

c

9

b

c

c

a

216

ab+ac+bc

12

c

a

b

c

a

12

b

c

a

b

c

217

a+bc

5

b

c

a

6

b

c

a

220

a(bc+bc)

7

b

c

a

b

c a

10

b

c

b

c

a

221

abc+bc

8

b

c

a

b

c

11+
12

b
c

c

a

b
b

c

b

a
c

222

abc+abc+abc

11

a

b

c

a

b c a

b c

18

b

c

a

c

a

b a

b c

223

abc+b(a+c)

13

c

a

b

b

c a

13

c

a

b

b

c

a

221+

abc+abc+abc

11

a

b

c

a

b c a

b c

18

a

c

a

b

b

c a

b c

225

abc+c(a+b)

13

a

b

c

c

a b

13

a

b

c

c

a

b

226

ab c +ab c +ab c +ab c

17

a

b

c

b

c a

17

a

b

c

b

c

a

227

ab+ac+bc+abc

18

a

b

a

c

b c a

b c

11

a

b

c

a

b

c a

b c

230

abc+bc

8

b

c

a

b

c

11+
12

b
b

c

a

b
c

c

b

a
c

231

bc+bc

9

b

c

b

c

.

9

b

c

b

c

232

c(a+b)+abc

13

b

a

c

b

c a

13

b

a

c

b

c

a

233

bc+b(a+c)

Ik

12

c

b

b
a

c
c

a
c

b

b

8

b

c

a

b

c

TABLE 1 (CONT'D).

Fen.
No.

Expression

NAND
Cct.

1

2

3

Inputs
456789

NOR
Cct.

1

2

3

Inputs

4 5 6 7 8 9

234

b(a+c)+abc

13

c

a

b

c

b

a

13

c

a

b

c

b a

235

bc+c(a+b)

14
12

b
c

c
a

b

b

a

b

c
c

8

b

c

a

b

c

236

c(a+b)+ab+abc

18

a

c

b

c

a

babe

11

a

b

c

a

b c a b c

237

a+bc+bc

10

b

c

b

c

a

7

a

b

c

a

b c

240

ac

4

a

c

1

a

c

241

ac+abc

8

a

c

a

b

c

14
12

c

b

a
c

b
a

c
c

a
a

242

c ( a+b )

6

b

a

c

5

a

b

c

243

ab+ac

9

a

b

a

c

9

a

c

a

b

244

ac+abc

8

a

c

a

b

c

14
12

c
c

a

b

c
a

a
c

b
a

245

ac+ac

9

a

c

a

c

9

a

c

a

c

246

c(b+a)+abc

13

a

b

c

a

c

b

13

a

b

c

a

c b

247

ac+a(b+c)

14

12

c
a

a

b

c
c

b
c

a
a

8

a

c

a

b

c

250

c ( a+b )

6

a

b

c

5

a

b

c

251

c(a+b)+abc

13

a

b

c

a

b

c

13

a

b

c

a

b c

252

c

c

c

253

ab+c

5

a

b

c

6

a

b

c

254

ab+ac

9

a

b

a

c

9

a

c

a

b

255

ac+bc+ac

14
12

c

b

a

a

b
c

c

c

a
a

8

a

c

a

b

c

256

ab+c

5

a

b

c

6

b

a

c

257

a+c

l

a

c

4

a

c

260

a(b+c)

6

b

c

a

5

c

b

a

261

bc+ac

9

b

c

a

c

9

a

c

b

c

262

bc+ab+ac

12

a

b

c

a

b

12

c

a

b

c

a

263

b+ac

5

c

a

b

6

c

a

b

264

a(b+c)+abc

13

c

b

a

c

a

b

13

c

b

a

c

a b

265

ac+c(a+b)

14
12

a
c

c

b

a
a

b

a

c
c

8

a

c

a

b

c

266

a(b+c)+bc+abc

18

a

b

a

c

b

c a b c

11

a

b

c

a

b c a b c

TABLE 1 (CONT'D).

Fen.

No.

Expression

267

ac+ac+b

270

ab+bc

271

bc+ac+bc

272

ab+c

273

b+c

27^

a(b+c)+ab

NAND Inputs NOR

Cct. 12 3^56789 Cct.

Inputs
123^56789

275 a(b+c)+a(b+c)

276

ab+ab+c

277

a+b+c

300

ab

301

ab+abc

302

ab+abc

303

ab+ab

30^

b(a+c)

305

ab+ac

306

b(a+c)+abc

307

ab+a(b+c)

310

b(a+c)

311

b(a+c)+abc

312

ab+ac

313

ab+ab +bc

31k

b

315

ac+b

316

ac+b

317

a+b

320

a(b+c)

10

a

c

a

c

b

9

b

a

b

c

Ik

c

b

a

c

b

12

a

b

c

c

b

5

b

a

c

1

b

c

Ik

a

b

c

a

b

12

c

b

a

a

b

15

a

b

c

a

b

c

16

a

c

b

c

a

b

10

a

b

a

b

c

2

a

b

c

k

a

b

8

a

b

a

b

c

a b c a b

9

a

b

a

b

6

a

c

b

9

a

b

a

c

13

a

c

b

a

b

c

ll+

b

a

b

c

a

12

a

c

b

b

a

6

a

c

b

13

c

a

b

c

a

b

9

a

b

a

c

Ik

b

a

c

b

a

12

c

a

b

b

a

b

5

a

c

b

5

a

c

b

1

a

b

6

c

b

a

7

a b

cab

c

9

b c

a b

8

b c

a b c

6

a b

c

k

b c

8

a b

cab

a b c a b c

7

c

a

b

c

a

b

3

a

b

c

1

a

b

Hi

a

b

c

a

b

12

c

a

b

a

b

Ik

a

b

a

b

c

12

a

c

b

a

b

9

a

b

a

b

5

a

c

b

9

a

b

a

c

13

a

c

b

a

b

c

8

a

b

a

b

c

15

c

a

b

13

c

a

b

c

a

b

9

a

b

a

c

8

a

b

a

b

c

b

6

c

a

b

6

a

c

b

k

a

b

5

b

c

a

TABLE 1 (COM 1 '!))

16

Fen.

NAND

Inputs

NOR

Inputs

No,

Expression

Cct.

1

2

3

k

5

6789

Cct,

1

2

3

k

5 6 7 8 9

321

ab+bc

9

a

b

b

c

9

a

b

b

c

322

a(b+c)+abc

13

b

c

a

b

a

c

13

b

c

a

b

a c

323

b ( a+c ) +ab

Ik

12

a
b

b
c

a
a

c

a

b
b

8

a

b

a

b

c

32+

ac+bc+ab

12

b

c

a

b

c

12

a

b

c

a

b

325

c+ab

5

a

b

c

6

a

b

c

326

a(b+c)+bc+abc

18

a

b

a

c

b

c a b c

11

a

b

c

a

b c a b c

327

ab+ab+c

10

a

b

a

b

c

7

a

b

c

a

b c

330

ac+bc

9

b

c

a

c

9

b

c

a

c

331

ab+bc+bc

Ik

12

b
a

c
c

a
b

b

b

c
c

8

b

c

a

b

c

332

c ( a+b ) +ac

ik

12

c

b

a
a

b
c

c

c

a
a

8

c

a

b

c

a

333

c ( a+b ) +c ( a+b )

15
16

c
c

a
b

b
a

c

b

a
c

b
a

7

b

c

a

b

c a

33^

ac+b

5

c

a

b

6

a

c

b

335

b+c

1

c

b

k

b

c

336

ac+ac+b

10

c

a

c

a

b

7

b

c

a

b

c a

337

a+b+c

2

c

a

b

3

b

c

a

3+0

a(b+c)

6

b

c

a

5

b

c

a

3kL

a(b+c)+abc

13

b

c

a

b

c

a

13

b

c

a

b

c a

342

ab+bc

9

b

c

b

a

9

a

b

c

b

3^3

ab+ab+ac

Ik

12

a
c

b
b

c

a

a

a

b
b

8

a

b

a

b

c

3kk

ac+bc

9

a

c

b

c

9

b

c

a

c

3^5

ac+ab+ac

Ik

12

a
b

c

c

b
a

a

a

c
c

8

a

c

a

b

c

3+6

b(a+c)+bc

1+
12

b
a

c
c

a
b

b
b

c
c

8

b

c

a

b

c

3^7

b(a+c)+b(a+c)

15
16

b
b

c

a

a
c

b
a

c

b

a
c

7

a

b

c

a

b c

350

ab+ac+bc

12

b

c

a

b

c

12

b

c

a

b

c

TABLE L (CONT'D)

Fen,

NAND

Inputs

NOR

Inputs

No.

Expression

Cct.

1

2

3

k

5

6 7 8 9

Cct.

1

2

3

1+56789

351

ab+ac+bc+abc

18

a

b

a

c

b

c a b c

11

a

b

c

a b c a b c

352

ab+c

5

a

b

c

6

a

b

c

353

ab+ab+c

10

a

b

a

b

c

7

c

a

b

cab

35^

ac+b

5

a

c

b

6

c

a

b

355

ac+ac+b

10

a

c

a

c

b

7

b

c

a

b c a

356

b+c

1

b

c

k

b

c

357

a+b+c

2

a

b

c

3

a

b

c

360

a

a

a

361

a+bc

5

b

c

a

6

b

c

a

362

a+bc

5

b

c

a

6

c

b

a

363

a+b

1

a

b

k

a

b

364

a+bc

5

c

b

a

6

b

c

a

365

a+c

1

a

c

k

a

c

366

a+bc+bc

10

c

b

b

c

a

7

a

b

c

a b c

367

a+b+c

2

a

b

c

3

a

b

c

370

a+bc

5

b

c

a

6

b

c

a

371

a+bc+bc

10

b

c

b

c

a

7

a

b

c

a b c

372

a+c

1

a

c

k

a

c

373

a+b+c

2

a

b

c

3

a

b

c

37^

a+b

1

a

b

h

a

b

375

a+b+c

2

a

b

c

3

a

b

c

376

a+b+c

2

a

b

c

3

a

b

c

377

1

1

1

5. CIRCUIT DIAGRAMS

Circuit 1

Circuit 2

Circuit 3

L

2

^L

3

i>-

^ 1

5 1

Circuit

8

Circuit 9

Circuit k

3-

Circuit 5

3-
Circuit 6

1
2

3

5
6

7
8
9

Circuit 10

Circuit 11

Circuit 7

3
,5

Circuit 12

-18-

3 -

k r

5 —

6 -

Circuit 13

Circuit 16

Circuit Ik

Circuit 17

Circuit 15

Circuit 1<

6. CONCLUSION.:

The results show that nearly all of the 256 functions of three
variables can be generated using four or fewer NOR or NAND elements, and that
that fan-out in all circuits is one. As in Hellerman's catalog, roughly half
of the NAND circuits are those which result when the minimum-OR polynomial is
rewritten in terms of the NAND connective. The analogous statement holds for
NOR circuits. It is speculated that this fraction will get smaller and smaller
as the number of variables in the function is increased. Nevertheless, the cir-
cuit obtained from the minimum-OR polynomial serves as a good starting point in
the search for a simple realization. One way in which the table could be used
when more variables are present would be to decompose the function and use the
circuits in the table to realize the constituents.

This catalog, along with the one by Hellerman, should prove useful in
the design of simple circuits. However, a more useful tool would be a computer
program capable of producing, in a reasonable length of time, a minimal circuit
for any arbitrary function. Perhaps such a program will be available in the
future .

-20-

BIBLIOGRAPHY

1. Earle, J., "Synthesizing Minimal Stroke and Dagger Functions," IRE Int.
Conv. Record , Part 2, pp. 55-65; i960.

2. Hellerman, L., "A Catalog of Three -Variable OR- Invert and AND- Invert Logical
Circuits," IEEE Trans, on Electronic Computers , Vol. EC-12, pp. 198-223;
June I963.

3. Maley, G. A., and J. Earle, The Logic Design of Transistor Digital
Computers , Prentice-Hall, Englewood Cliffs, N.J., Chap. 6; 1963.

4. Scott, N. R., Analog and Digital Computer Technology , McGraw-Hill, New York,
pp. ^31-^38; I960.

5. Shubert, E. J., "Logical Design by Regression," Trans. AIEE , Vol, 80
(Commun. and Electronics, No. 56), pp. 380- 383; September I96I.

-21-

a/

JVH 2 8 1969

```